package binaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Offer34 {

        ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
    public List<List<Integer>> pathSum1(TreeNode root, int target) {
        postTraverse(root, target);
        return list;
    }
    ArrayList<Integer> temp = new ArrayList<Integer>();
    int sum = 0;
    public void postTraverse(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        temp.add(root.val);
        sum += root.val;
        if (root.left == null && root.right == null && sum == target) {
            list.add(temp);
        }
        postTraverse(root.left, target);
        postTraverse(root.right, target);
        sum -= root.val;
        temp.remove(temp.size() - 1);

    }

    LinkedList<List<Integer>> result=new LinkedList<List<Integer>>();
    LinkedList<Integer> path=new LinkedList<Integer>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root,target);
        return result;
    }
    void recur(TreeNode root, int target) {
        if(root!=null){
            path.add(root.val);
            target-=root.val;
            if(target==0&&root.left==null&&root.right==null){//遍历到叶节点且目标值正好等于路径之和
                LinkedList<Integer> path_temp=new LinkedList<Integer>(path);
                result.add(path_temp);
            }
            recur(root.left,target);
            recur(root.right,target);
            path.removeLast();//回退时将当前元素出栈
        }
    }


}


